package DP_300;

import java.util.Arrays;

public class Solution {
	public int lengthOfLIS_DP(int[] nums) {
		int len = nums.length;
		if (len < 2) {
			return len;
		}
		int[] top = new int[len];
		Arrays.fill(top, 1);
		for (int i = 1; i < len; i++) {
			for (int j = 0; j < i; j++) {
				if (nums[i] > nums[j]) {
					top[i] = Math.max(top[i], top[j] + 1);
				}
			}
		}
		int res = top[0];
		for (int i = 0; i < top.length; i++) {
			res = Math.max(res, top[i]);
		}
		return res;

	}

	public int lengthOfLIS_BS(int[] nums) {
		int piles = 0;
		int[] top = new int[nums.length];
		for (int poker : nums) {
			int left = 0, right = piles;
			while (left < right) {
				int mid = left + (left + right) / 2;
				if (top[mid]<poker) {
					left =mid+1;
				}else {
					right = mid;
				}
			}
			top[left] = poker;
			if (left == piles ) {
				piles++;
			}
		}
		return piles;
	}
}
